import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

import javax.xml.transform.Templates;


public class Mixer {
	Set<String> checkSet;
	ArrayList<String> anonymitySet;
	ArrayList<ArrayList<String>> savedSets;
	ArrayList<String> communicationPartners; //alice communication partenrs
	Random rand;
	int N=5000; //The total number of users in the anonymity syste, includes alice
	int m=10; //nbr of: alice comunication partners
	int b=3; //senders each batch
	public Mixer(){
		rand=new Random();
		checkSet=new HashSet<String>();
		anonymitySet=new ArrayList<String>();
		savedSets=new ArrayList<ArrayList<String>>();
		communicationPartners=new ArrayList<String>();
		
		int nbrOfSimulations=10;
		ArrayList<Integer> results=simulate(nbrOfSimulations);
		int c=0;
		int failures=0;
		int sucesses=0;
		for(int i:results){
			if(i>300){
				failures++;
			}else{
				c+=i;
				sucesses++;
			}
		}
		int avgCSucess=c/sucesses;
		System.out.println("Avg complexity for a success: "+ avgCSucess+" failure frequency: "+failures+"/"+nbrOfSimulations);
	}
	private ArrayList<Integer> simulate(int times){
		ArrayList<Integer> complexityResults=new ArrayList<Integer>();
		//reset

		for(int k=0;k<times;k++){
			int complexity=0;
			checkSet.clear();
			anonymitySet.clear();
			savedSets.clear();
			communicationPartners.clear();
			for(int i=0;i<N-1;i++){
				anonymitySet.add("user"+i);
			}
			anonymitySet.add("alice");
			communicationPartners=getRandomSubSet(anonymitySet, m, true); //One could be alice
			Collections.sort(communicationPartners);
			while(savedSets.size()<communicationPartners.size()){
				complexity+=observeNewBatch();
				if(complexity>300){ //Maximum complexity reached
					break;
				}
			}
			excludingPhase();
			ArrayList<String> result=new ArrayList<String>();
			for(ArrayList<String> list:savedSets){
				result.add(list.get(0));
			}
			boolean disclosiureSuccess=result.equals(communicationPartners);
			complexityResults.add(complexity);
		}
		return complexityResults;
	}
	private void excludingPhase() {
		while(!exclusionDone()){
			ArrayList<String> R=getRandomSubSet(anonymitySet, b-1, false); //Recievers for the none alice senders
			R.addAll(getRandomSubSet(communicationPartners, 1, true)); //add a reciever for alice package
			for(int i=0;i<savedSets.size();i++){
				if(!intersectionIsEmpty(R,savedSets.get(i))){
					boolean allIntersectionsEmpty=true;
					for(int j=0;j<savedSets.size();j++){
						if(j!=i){
							if(!intersectionIsEmpty(R, savedSets.get(j))){
								allIntersectionsEmpty=false;
								break;
							}
						}
					}
					//intersection with R was empty for all sets != Ri
					if(allIntersectionsEmpty){
						savedSets.set(i, getIntersection(R, savedSets.get(i)));
					}
				}	
			}
		}
	}
	private boolean exclusionDone() {
		for(ArrayList<String> list:savedSets){
			if(list.size()!=1){
				return false;
			}
		}
		return true;
	}
	private ArrayList<String> getIntersection(ArrayList<String> r,
			ArrayList<String> r2) {
		ArrayList<String> intersection=new ArrayList<String>();
		for(String s: r){
			if(r2.contains(s)){
				intersection.add(s);
			}
		}
		return intersection;
	}
	private boolean intersectionIsEmpty(ArrayList<String> r,
			ArrayList<String> r2) {
		return getIntersection(r, r2).size()==0;
	}
	public ArrayList<String> getRandomSubSet(ArrayList<String> set, int n, boolean unique){
		if(n>=set.size()){
			System.out.println("the whole set was selected");
			return set;
		}
		ArrayList<String> subSet=new ArrayList<String>();
		ArrayList<String> notSelected=(ArrayList<String>) set.clone();
		for(int i=0;i<n;i++){

			int select=rand.nextInt(notSelected.size());
			subSet.add(notSelected.get(select));
			if(unique){
				notSelected.remove(select);
			}
		}
		return subSet;
	}
	public int observeNewBatch(){
		int complexity=0;
		ArrayList<String> senders=getRandomSubSet(anonymitySet, b, true);
		if(senders.contains("alice")){
			complexity++;
			//			System.out.println(c);
			//System.out.println("Alice was in batch");
			ArrayList<String> R=getRandomSubSet(anonymitySet, b-1, false); //Recievers for the none alice senders
			R.addAll(getRandomSubSet(communicationPartners, 1, true)); //add a reciever for alice package
			Set<String> tmpSet=new HashSet<String>();
			tmpSet.addAll(checkSet);
			int prevSize=tmpSet.size();
			tmpSet.addAll(R);
			if(tmpSet.size()-prevSize==b){ //R and all previous Rs are mutally disjoint
				savedSets.add(R);
				checkSet=tmpSet;
			}

		}
		return complexity;
	}
}
